package com.zy.skip;

import java.util.Optional;
import java.util.Random;

/**
 *
 * __|__ __|__
 * _|_   _|_
 * .---. .---.
 * |___| |___|
 * _\_/_ _\_/_
 * _X_   _X_
 * |   | |   |
 * |___| |___|
 *
 * @description: 跳表V2 (注意不能存放NUll)
 * @author: zhaoyi
 * @create: 2020-04-16 13:57
 * <p>
 * 第一步 定义Node和 一些字段 构造方法
 * 第二步 一些辅助方法
 * 1 随机函数,是否添加索引 randomFunction()
 * 2 水平方向插入元素 insertLine()
 * 3 垂直方向插入元素 insertUpDown()
 * 4 创建一个空的索引行 createEmptyLevel()
 * 第三步: 重要的查找对象函数 findEntry(T value, Node startNode)（插入删除都要用到）
 * 第四步: 添加函数 add(T value)
 * 第五步: 删除函数 erase(T value)
 **/

public class SkipListV2<T extends Comparable<? super T>> {

    /**
     * 第一步 定义Node和 一些字段 构造方法
     */
    class Node {
        private final T val;
        //定义指向上下左右的指针
        private Node left, right, up, down;

        public Node(T val) {
            this.val = val;
        }
    }

    //跳表的层级
    private int levels;
    /**
     * 最上层索引的头和尾
     * 创建新的一层索引时会更新
     */
    private Node head;
    private Node tail;

    public SkipListV2() {
        this.levels = 0;
        this.head = new Node(null);
        this.tail = new Node(null);
        head.right = tail;
        tail.left = head;
    }

    /**
     * 随机函数,是否添加索引
     * 每次插入元素的时候，都进行一次 50% 概率的判断，如果 true 则向上层添加一个索引，如果 false 就不加了
     */
    private Random random = new Random();

    private boolean randomFunction() {
        return random.nextBoolean();
    }

    /**
     * 水平方向插入元素
     *
     * @param target 要插入的节点对象
     * @param source 插入到该节点后面
     */
    private void insertLine(Node target, Node source) {
        source.right.left = target;
        target.right = source.right;
        source.right = target;
        target.left = source;
    }

    /**
     * 竖直方向插入元素
     *
     * @param target 要插入的节点对象
     * @param source 插入到该节点上方
     */
    private void insertUpDown(Node target, Node source) {
        source.up = target;
        target.down = source;
    }

    /**
     * 向上一层创建索引
     */
    private void createEmptyLevel() {
        Node newHead = new Node(null);
        Node newTail = new Node(null);

        //上下链接
        insertUpDown(newHead, this.head);
        insertUpDown(newTail, this.tail);

        //新索引左右链接
        newHead.right = newTail;
        newTail.left = newHead;

        //更新最上层的头尾指针和等级
        this.head = newHead;
        this.tail = newTail;
        this.levels += 1;
    }


    /**
     * 查找对应值的节点,找不到时返回小于value的最大值
     *
     * @param value
     * @param startNode
     * @return
     */
    private Node findEntry(T value, Node startNode) {

        //一定要有等于
        while (startNode.right.val != null && startNode.right.val.compareTo(value) <= 0) {
            startNode = startNode.right;
        }
        if (startNode.down != null) {
            return findEntry(value, startNode.down);
        }
        return startNode;
    }

    //是否存在t
    public boolean search(T value) {
        return Optional.ofNullable(findEntry(value, this.head))
                .filter(f -> f.val != null)
                .map(f -> f.val.equals(value))
                .orElse(false);
    }

    //添加元素
    public void add(T value) {
        //找到添加的位置
        Node entry = findEntry(value, this.head);
        //添加到低层
        Node addNode = new Node(value);
        insertLine(addNode, entry);

        int levelsCurrent = 1;
        //是否添加到上层索引
        while (randomFunction()) {
            //若上层索引不存在新建一个
            if (this.levels < levelsCurrent) {
                createEmptyLevel();
            }

            //索引层插入
            Node node = new Node(value);
            //如果entry的up为null的话,需要右边移动
            while (entry.up == null){
                entry = entry.left;
            }
            insertLine(node, entry.up);
            insertUpDown(node, addNode);

            //假如再次往上级插入,建立上下连接的target为本层新加入的节点了
            //同时 entry也要调整
            addNode = node;
            entry = entry.up;

            levelsCurrent++;

        }

    }

    //删除返回是否删除成功
    public boolean erase(T value) {
        Node entry = findEntry(value, head);
        return Optional.ofNullable(entry)
                .filter(f -> f.val != null && f.val.equals(value))
                .map(f -> {
                    while (f != null) {
                        //删除本层
                        f.left.right = f.right;
                        f.right.left = f.left;
                        //指向上一层
                        f = f.up;
                    }
                    return true;
                }).orElse(false);

    }


}
